/*
 * @lc app=leetcode.cn id=661 lang=cpp
 *
 * [661] 图片平滑器
 */
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>

using namespace std;
// @lc code=start
class Solution {
public:
    vector<vector<int>> imageSmoother(vector<vector<int>>& img) {
        //朴素算法会重复计算多次，另一种方法是前缀和，对其进行优化
        int m = img.size();
        int n=img[0].size();
        vector<vector<int>> dp(m+1, vector<int>(n+1));
        vector<vector<int>> ret(m, vector<int>(n));
        //计算前缀和
        for(int i=1;i<=m;i++)
            for(int j=1;j<=n;j++)
                dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + img[i-1][j-1];
        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++){
                //限定边界
                int x1=max(i-1,0), y1=max(j-1,0), x2=min(i+2,m), y2=min(j+2,n);
                ret[i][j] = (dp[x2][y2]-dp[x2][y1]-dp[x1][y2]+dp[x1][y1]) / ((x2-x1)*(y2-y1));
            }
        return ret;
    }
};
// @lc code=end

//!朴素算法
// vector<vector<int>> direct = {{-1,-1},{0,-1},{1,-1},{-1,0},{0,0},{1,0},{-1,1},{0,1},{1,1}};
// int m = img.size();
// int n = img[0].size();
// int sum = 0;
// int count = 0;
// vector<vector<int>> ret(m,vector<int>(n));
// for(int i = 0;i < m;i++) {
//     for(int j = 0;j < n;j++) {
//         sum = 0,count = 0;
//         for(auto d : direct) {
//             int new_i = i + d[0];
//             int new_j = j + d[1];
//             if(new_i >= 0 && new_i < m && new_j >= 0 && new_j < n) {
//                 sum += img[new_i][new_j];
//                 count++;
//             }
//         }
//         ret[i][j] = sum/count;
//     }
// }
// return ret;
